//给定字符串 s 和 t ，判断 s 是否为 t 的子序列。 
//
// 字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而
//"aec"不是）。 
//
// 进阶： 
//
// 如果有大量输入的 S，称作 S1, S2, ... , Sk 其中 k >= 10亿，你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代
//码？ 
//
// 致谢： 
//
// 特别感谢 @pbrother 添加此问题并且创建所有测试用例。 
//
// 
//
// 示例 1： 
//
// 
//输入：s = "abc", t = "ahbgdc"
//输出：true
// 
//
// 示例 2： 
//
// 
//输入：s = "axc", t = "ahbgdc"
//输出：false
// 
//
// 
//
// 提示： 
//
// 
// 0 <= s.length <= 100 
// 0 <= t.length <= 10^4 
// 两个字符串都只由小写字符组成。 
// 
// Related Topics 双指针 字符串 动态规划 👍 655 👎 0

package leetcode.editor.cn;
//leetcode submit region begin(Prohibit modification and deletion)
class Solution392 {
    public boolean isSubsequence1(String s, String t) {
        //dp[i][j] 表示以下标i-1为结尾的字符串s，和以下标j-1为结尾的字符串t，相同子序列的长度为dp[i][j]。
//        有同学问了，为啥要表示下标i-1为结尾的字符串呢，为啥不表示下标i为结尾的字符串呢？
//        用i来表示也可以！
//        但我统一以下标i-1为结尾的字符串来计算，这样在下面的递归公式中会容易理解一些，如果还有疑惑，可以继续往下看。
        //如果要是定义的dp[i][j]是以下标i为结尾的字符串s和以下标j为结尾的字符串t，初始化就比较麻烦了。
        boolean[][] dp = new boolean[s.length()+1][t.length()+1];
        //初始化,当s为空时，总是t的子序列
        for(int i= 0; i <= t.length(); i++){
            dp[0][i] = true;
        }
        for(int i = 1; i <= s.length(); i++){ //以第i个字符结尾的s
            for(int j = i; j <= t.length(); j++){ //以第j个字符结尾的t,j从i开始效率更高
                if(s.charAt(i-1) == t.charAt(j-1)){ //判断以第i个字符结尾的s是否是以第j个字符结尾的t的子序列
                    dp[i][j] = dp[i-1][j-1];
                } else { //继续判断以第i个字符结尾的s是否是以第j-1个字符结尾的t的子序列
                    dp[i][j] = dp[i][j-1];
                }
            }
        }
        return dp[s.length()][t.length()];
    }

    /**
     * 双指针
     * @param s
     * @param t
     * @return
     */
    public boolean isSubsequence(String s, String t) {
        if(s.length() > t.length()) return false;
        int i = 0, j = 0;
        while(i <= s.length()-1 && j <= t.length()-1){
            if(s.charAt(i)==t.charAt(j)){
                i++;
                j++;
            } else {
                j++;
            }
        }
        return  i == s.length();
    }

    public static void main(String[] args) {
        new Solution392().isSubsequence("ace","abcde");
    }
}
//leetcode submit region end(Prohibit modification and deletion)
